package leetcode_core.leetcode_2;

import java.util.List;

public class ReverseKGroup {
    class ListNode <V>{
        V val;
        ListNode next;
        ListNode() {}
        ListNode(V val) { this.val = val; }
        ListNode(V val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start  = head;
        ListNode end = getKEnd(start, k);
        if(end == null){//不够k个一组
            return start;//返回老头部
        }
        //第一组凑齐了,如果我们现在的链表是a->b->c,我们最终返回的链表头部一定是反转之后的头部
        head = end;
        reverse(start,end);
        //我们知道a(start)->b->c(end)是初始状态,进入reverse之后end会移动到下一个位置
        //然后反转之后,变成:c->b->a(start),然后咱们的下一段链表的上一个节点就是a,start已经默认连到下一个节点了
        ListNode lastEnd = start;
        while (lastEnd.next!=null){
            start = lastEnd.next;
            end = getKEnd(start,k);
            if(end == null){
                return head;
            }
            reverse(start,end);
            lastEnd.next = end;
            lastEnd = end;
        }
        return head;
    }

    public void reverse(ListNode start,ListNode end){
        //翻转的方法,从start开始,一直走到end,将路径上的所有节点进行翻转
        //翻转的步骤
        end = end.next;//结束节点
        ListNode pre = null;
        ListNode next = null;
        ListNode cur = start;
        while (cur != end){
            next = cur.next;    //第一步,先记录当前节点的下一个节点
            cur.next = pre;     //修改指针,让指针指向上一个节点
            pre = cur;          //第二步,让上一个节点等于当前节点
            cur = next;         //第三步,搜索指针步进
        }
        //完成了组内的逆序之后,得到一个新的节点,这个节点是逆序之后的最后一个节点
        //比如说原来是1 2 3
        //那么逆序之后就会返回3(head) 2 1
        //这里确保pre不会是空
        start.next = end;
    }

    public ListNode getKEnd(ListNode start,int k){
        while (--k !=0 && start!= null){start = start.next;}
        return start;
    }




}
